/**
 * 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。
 * @param nums 
 * @param target 
 */
 const searchRange = (nums: number[], target: number): number[] => {
    // 边界判断
    if (nums.length <= 1) return [-1, -1]

    const len = nums.length;

    let s = 0,
        e = len;

    while (s < e) {
        // 获取中间位置
        const m = (s + e) >> 1;

        if (nums[m] === target) {
            // 找到了, 往左往后查找左右的边界
            let l = m - 1;
            // 直到l 不等于target, l + 1就是最后的位置
            while (nums[l] == target) l--;

            let r = m + 1;
            // r - 就是最后的位置
            while (nums[r] === target) r++;

            return [l + 1, r - 1]
        } else if (nums[m] > target){ 
            // 往前找
            e = m;
        } else {
            // 往后找
            s = m + 1
        }

    }

    return [-1, -1]
};


const searchRange2 = (nums: number[], target: number): number[] => {
    // 边界判断
    if (nums.length <= 1) return [-1, -1]

    const len = nums.length;
    let start = -1,
        end = -1
    for (let i = 0; i < len; i++) {
        if (nums[i] === target) {
            start = i
            break;
        }
    }

    for (let i = len - 1; i >= 0; i--) {
        if (nums[i] === target) {
            end = i
            break;
        }
    }

    if (start !== -1 && end !== -1) {
        return [start, end]
    } else if (start !== -1) {
        return [start, start]
    } else if (end !== -1) {
        return [end, end]
    } else {    
        return [-1, -1]
    }

};